#include "bfs.h"
#include "climits"

BFS::BFS() : parent(0), distance(0), dRow(0), pRow(0), graph(0)
{

}

void BFS::setGraph(const Graph &g)
{
	if (graph) delete graph;

	this->graph = new Graph(g);

	if (parent) delete parent;
	if (distance) delete distance;

	parent = new Matrix<int,int>(graph->getSize());
	distance = new Matrix<int, int>(graph->getSize());

	int *header = new int[graph->getSize()];
	for (unsigned int i=0; i<graph->getSize(); ++i)
	{
		header[i]=(*graph)[i].data;
	}
	parent->setHead(header);
	distance->setHead(header);
}

void BFS::init(const Graph_Node& start)
{
	if (graph)
	{
		queue.clear();
		if (dRow) delete [] dRow;
		if (pRow) delete [] pRow;
		dRow = new int[graph->getSize()];
		pRow = new int[graph->getSize()];
		for (unsigned int i=0;i<graph->getSize();++i)
		{
			pRow[i] = 0;
			if ((*graph)[i] == start)
			{
				(*graph)[i].color = black;
				queue.push((*graph)[i]);
				dRow[i] = 0;
			}
			else
			{
				dRow[i] = INT_MAX;
				(*graph)[i].color = white;
			}
		}
		parent->addRow(pRow);
		distance->addRow(dRow);
	}
}

void BFS::start()
{
	if (graph)
	{
		while (!queue.isEmpty())
		{
			Graph_Node node = queue.front();
			queue.pop();

			std::cout << node.data << " ";

			int uIndex = graph->getIndexOf(node);

			Graph_Node *v =	node.next;

			while (v)
			{
				int vIndex = graph->getIndexOf(*v);
				if ((*graph)[vIndex].color!=black)
				{	
					queue.push((*graph)[vIndex]);
					(*graph)[vIndex].color = black;
					dRow[vIndex] = dRow[uIndex]+1;
					pRow[vIndex] = node.data;
				}
				v=v->next;
			}

			parent->addRow(pRow);
			distance->addRow(dRow);
		}
		std::cout << "Parent:" << std::endl << *parent << std::endl << "Distance: " << std::endl;
		std::cout << *distance << std::endl;
	}
}

const Graph& BFS::getGraph() const
{
	return *graph;
}